/*
 * (C) Copyright 2014-2016, by Dimitrios Michail
 *
 * JHeaps Library
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.jheaps.tree

import org.jheaps.AddressableHeap
import org.jheaps.annotations.ConstantTime
import org.jheaps.annotations.LogarithmicTime
import java.io.Serializable
import java.util.*
import kotlin.Comparator

/**
 * An explicit binary tree addressable heap. The heap is sorted according to the
 * [natural ordering][Comparable] of its keys, or by a
 * [Comparator] provided at heap creation time, depending on which
 * constructor is used.
 *
 *
 *
 * The worst-case cost of `insert`, `deleteMin`, `delete` and
 * `decreaceKey` operations is O(log(n)) and the cost of `findMin`
 * is O(1).
 *
 *
 *
 * Note that the ordering maintained by a binary heap, like any heap, and
 * whether or not an explicit comparator is provided, must be *consistent
 * with `equals`* if this heap is to correctly implement the
 * `Heap` interface. (See `Comparable` or `Comparator` for a
 * precise definition of *consistent with equals*.) This is so because
 * the `Heap` interface is defined in terms of the `equals`
 * operation, but a binary heap performs all key comparisons using its
 * `compareTo` (or `compare`) method, so two keys that are deemed
 * equal by this method are, from the standpoint of the binary heap, equal. The
 * behavior of a heap *is* well-defined even if its ordering is
 * inconsistent with `equals`; it just fails to obey the general contract
 * of the `Heap` interface.
 *
 *
 *
 * **Note that this implementation is not synchronized.** If
 * multiple threads access a heap concurrently, and at least one of the threads
 * modifies the heap structurally, it *must* be synchronized externally.
 * (A structural modification is any operation that adds or deletes one or more
 * elements or changing the key of some element.) This is typically accomplished
 * by synchronizing on some object that naturally encapsulates the heap.
 *
 * @param <K>
 * the type of keys maintained by this heap
 * @param <V>
 * the type of values maintained by this heap
 *
 * @author Dimitrios Michail
 *
 * @see AddressableHeap
 *
 * @see Comparable
 *
 * @see Comparator
</V></K> */
class BinaryTreeAddressableHeap<K, V> @JvmOverloads constructor(
    /**
     * The comparator used to maintain order in this heap, or null if it uses
     * the natural ordering of its keys.
     *
     * @serial
     */
    private val comparator: Comparator<in K?>? = null
) :
    AddressableHeap<K, V>, Serializable {

    /**
     * Size of the heap
     */
    private var size: Long

    /**
     * Root node of the heap
     */
    private var root: Node?

    /**
     * Constructs a new, empty heap, ordered according to the given comparator.
     *
     *
     *
     * All keys inserted into the heap must be *mutually comparable* by
     * the given comparator: `comparator.compare(k1,
     * k2)` must not throw a `ClassCastException` for any keys `k1`
     * and `k2` in the heap. If the user attempts to put a key into the
     * heap that violates this constraint, the `insert(Object key)` call
     * will throw a `ClassCastException`.
     *
     * @param comparator
     * the comparator that will be used to order this heap. If
     * `null`, the [natural ordering][Comparable] of
     * the keys will be used.
     */
    /**
     * Constructs a new, empty heap, using the natural ordering of its keys.
     *
     *
     *
     * All keys inserted into the heap must implement the [Comparable]
     * interface. Furthermore, all such keys must be *mutually
     * comparable*: `k1.compareTo(k2)` must not throw a
     * `ClassCastException` for any keys `k1` and `k2` in the
     * heap. If the user attempts to put a key into the heap that violates this
     * constraint (for example, the user attempts to put a string key into a
     * heap whose keys are integers), the `insert(Object key)` call will
     * throw a `ClassCastException`.
     */
    init {
        this.size = 0
        this.root = null
    }

    /**
     * {@inheritDoc}
     */
    @LogarithmicTime
    override fun insert(key: K): Node {
        return insert(key, null)
    }

    /**
     * {@inheritDoc}
     */
    @LogarithmicTime
    override fun insert(key: K, value: V?): Node {
        if (key == null) {
            throw NullPointerException("Null keys not permitted")
        }
        val n = Node(key, value)

        // easy special cases
        if (size == 0L) {
            root = n
            size = 1
            return n
        } else if (size == 1L) {
            val c: Int
            if (comparator == null) {
                c = (key as Comparable<K>).compareTo(root!!.key)
            } else {
                c = comparator.compare(key, root!!.key)
            }
            if (c < 0) {
                n.o_c = root
                root!!.y_s = n
                root = n
            } else {
                root!!.o_c = n
                n.y_s = root
            }
            size = 2
            return n
        }

        // find parent of last node and hang
        val p: Node = findParentNode(size + 1)
        if (p.o_c == null) {
            p.o_c = n
        } else {
            p.o_c!!.y_s = n
        }
        n.y_s = p

        // increase size
        size++

        // fix priorities
        fixup(n)

        return n
    }

    /**
     * {@inheritDoc}
     */
    @ConstantTime
    override fun findMin(): Node {
        if (size == 0L) {
            throw NoSuchElementException()
        }
        return root!!
    }

    /**
     * {@inheritDoc}
     */
    @LogarithmicTime
    override fun deleteMin(): Node {
        if (size == 0L) {
            throw NoSuchElementException()
        }
        val oldRoot: Node = root!!

        // easy special cases
        if (size == 1L) {
            root = null
            size = 0
            return oldRoot
        } else if (size == 2L) {
            root = root!!.o_c
            root!!.o_c = null
            root!!.y_s = null
            size = 1
            oldRoot.o_c = null
            return oldRoot
        }

        // remove last node
        val lastNodeParent: Node = findParentNode(size)
        var lastNode = lastNodeParent.o_c!!
        if (lastNode.y_s !== lastNodeParent) {
            val tmp = lastNode
            lastNode = tmp.y_s!!
            tmp.y_s = lastNodeParent
        } else {
            lastNodeParent.o_c = null
        }
        lastNode.y_s = null

        // decrease size
        size--

        // place it as root
        // (assumes root.o_c exists)
        if (root!!.o_c!!.y_s === root) {
            root!!.o_c!!.y_s = lastNode
        } else {
            root!!.o_c!!.y_s!!.y_s = lastNode
        }
        lastNode.o_c = root!!.o_c
        root = lastNode

        // fix priorities
        fixdown(root!!)

        oldRoot.o_c = null
        return oldRoot
    }

    @get:ConstantTime
    override val isEmpty: Boolean
        get() {
            return size == 0L
        }

    /**
     * {@inheritDoc}
     */
    @ConstantTime
    override fun size(): Long {
        return size
    }

    /**
     * {@inheritDoc}
     */
    override fun comparator(): Comparator<in K?>? {
        return comparator
    }

    /**
     * {@inheritDoc}
     */
    @ConstantTime
    override fun clear() {
        root = null
        size = 0
    }

    // handle
   inner class Node(override var key: K, override var value: V?) : AddressableHeap.Handle<K, V>, Serializable {
        var o_c: Node? = null // older child
        var y_s: Node? = null // younger sibling or parent

        @LogarithmicTime
        override fun decreaseKey(newKey: K) {
            if (this !== root && y_s == null) {
                throw IllegalArgumentException("Invalid handle!")
            }
            val c: Int
            if (comparator == null) {
                c = (newKey as Comparable<K>).compareTo(key)
            } else {
                c = comparator.compare(newKey, key)
            }

            if (c > 0) {
                throw IllegalArgumentException("Keys can only be decreased!")
            }
            key = newKey
            if (c == 0 || root === this) {
                return
            }
            fixup(this)
        }

        @LogarithmicTime
        override fun delete() {
            if (this !== root && y_s == null) {
                throw IllegalArgumentException("Invalid handle!")
            }

            var p: Node? = getParent(this)
            while (p != null) {
                val pp: Node? = getParent(p)
                swap(this, p, pp)
                p = pp
            }

            // remove root
            deleteMin()
            o_c = null
            y_s = null
        }

    }

    private fun fixup(n: Node) {
        if (comparator == null) {
            var p: Node? = getParent(n)
            while (p != null) {
                if ((n.key as Comparable<K>).compareTo(p.key) >= 0) {
                    break
                }
                val pp: Node? = getParent(p)
                swap(n, p, pp)
                p = pp
            }
        } else {
            var p: Node? = getParent(n)
            while (p != null) {
                if (comparator.compare(n.key, p.key) >= 0) {
                    break
                }
                val pp: Node? = getParent(p)
                swap(n, p, pp)
                p = pp
            }
        }
    }

    private fun fixdown(n: Node) {
        if (comparator == null) {
            var p: Node? = getParent(n)
            while (n.o_c != null) {
                var child: Node = n.o_c!!
                if (child.y_s !== n && (child.y_s!!.key as Comparable<K>).compareTo(child.key) < 0) {
                    child = child.y_s!!
                }
                if ((n.key as Comparable<K>).compareTo(child.key) <= 0) {
                    break
                }
                swap(child, n, p)
                p = child
            }
        } else {
            var p: Node? = getParent(n)
            while (n.o_c != null) {
                var child: Node = n.o_c!!
                if (child.y_s !== n && comparator.compare(child.y_s!!.key, child.key) < 0) {
                    child = child.y_s!!
                }
                if (comparator.compare(n.key, child.key) <= 0) {
                    break
                }
                swap(child, n, p)
                p = child
            }
        }
    }

    /*
     * Get the parent node of a given node.
     */
    private fun getParent(n: Node): Node? {
        if (n.y_s == null) {
            return null
        }
        val c: Node = n.y_s!!
        if (c.o_c === n) {
            return c
        }
        val p1 = c.y_s
        if (p1 != null && p1.o_c === n) {
            return p1
        }
        return c
    }

    /*
     * Start at the root and traverse the tree in order to find the parent node
     * of a particular node. Uses the bit representation to keep the cost
     * log(n).
     * 
     * @param node the node number assuming that the root node is number one
     */
    private fun findParentNode(node: Long): Node {
        // assert node > 0;

        // find bit representation of node

        val s: LongArray = longArrayOf(node)
        val bits: BitSet = BitSet.valueOf(s)

        // traverse path to last node
        var cur: Node = root!!
        for (i in bits.length() - 2 downTo 1) {
            cur = if (bits.get(i)) {
                cur.o_c!!.y_s!!
            } else {
                cur.o_c!!
            }
        }
        return cur
    }

    /*
     * Swap a node with its parent which must be the root.
     */
    private fun swap(n: Node, root: Node) {
        // assert this.root == root;

        val nLeftChild = n.o_c
        if (root.o_c === n) {
            if (n.y_s === root) {
                // n is left child and no right sibling
                n.o_c = root
                root.y_s = n
            } else {
                // n is left child and has right sibling
                root.y_s = n.y_s
                root.y_s!!.y_s = n
                n.o_c = root
            }
        } else {
            // n is right child
            root.o_c!!.y_s = root
            n.o_c = root.o_c
            root.y_s = n
        }
        n.y_s = null

        // hang children
        root.o_c = nLeftChild
        if (nLeftChild != null) {
            if (nLeftChild.y_s === n) {
                nLeftChild.y_s = root
            } else {
                nLeftChild.y_s!!.y_s = root
            }
        }
        this.root = n
    }

    /*
     * Swap a node with its parent
     * 
     * @param n the node
     * 
     * @param p the parent node
     * 
     * @param pp the parent of the parent node, maybe null
     */
    private fun swap(n: Node, p: Node, pp: Node?) {
        if (pp == null) {
            swap(n, p)
            return
        }

        val nLeftChild = n.o_c
        if (pp.o_c === p) {
            // p left child of pp
            if (p.o_c === n) {
                if (n.y_s === p) {
                    // n left child of p and no sibling
                    pp.o_c = n
                    n.y_s = p.y_s
                    n.o_c = p
                    p.y_s = n
                } else {
                    // n left child or p and sibling
                    n.y_s!!.y_s = n
                    val tmp = n.y_s
                    n.y_s = p.y_s
                    p.y_s = tmp
                    pp.o_c = n
                    n.o_c = p
                }
            } else {
                // n right child of p
                val tmp = p.o_c!!
                n.y_s = p.y_s
                pp.o_c = n
                n.o_c = tmp
                tmp.y_s = p
                p.y_s = n
            }
        } else {
            // p right child of pp
            if (p.o_c === n) {
                if (n.y_s === p) {
                    // n left child of p and no sibling
                    n.y_s = pp
                    pp.o_c!!.y_s = n
                    n.o_c = p
                    p.y_s = n
                } else {
                    // n left child of p and sibling
                    pp.o_c!!.y_s = n
                    p.y_s = n.y_s
                    n.y_s = pp
                    n.o_c = p
                    p.y_s!!.y_s = n
                }
            } else {
                // n right child of p
                pp.o_c!!.y_s = n
                n.y_s = pp
                n.o_c = p.o_c
                n.o_c!!.y_s = p
                p.y_s = n
            }
        }

        // hang children
        p.o_c = nLeftChild
        if (nLeftChild != null) {
            if (nLeftChild.y_s === n) {
                nLeftChild.y_s = p
            } else {
                nLeftChild.y_s!!.y_s = p
            }
        }
    }

}
